package com.heima.datastructure.deque;

import java.util.ArrayDeque;
import java.util.Iterator;

/**
 * 用循环数组实现双端队列
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/2 9:06
 */
public class ArrayDeque1<E> implements Deque<E>, Iterable<E> {
    private E[] arr; // 循环数组
    private int head; // 头指针，指向双端队列最左端元素，成员变量int不赋初值默认是0
    private int tail; // 尾指针，指向双端队列最右端元素的下一个元素，成员变量int不赋初值默认是0

    /**
     * 用构造方法初始化数组，head和tail会自动初始化的
     *
     * @param capacity 容量
     */
    @SuppressWarnings("all")
    public ArrayDeque1(int capacity) {
        arr = (E[]) new Object[capacity + 1]; // tail会占一个位置
    }

    /**
     * <h3>包级私有，当前包其他类可访问此方法，外部不可访问</h3>
     * <h3>而且此方法与当前类的实例无关，所以加static，而且可以与实例方法区分开来</h3>
     * <strong>不加private修饰以及增加一个capacity变量是为了破坏封装性，在同一个包内都能使用此方法进行已知容量的数组索引自增操作</strong><br><br>
     * 处理每次右端入队或者左端出队时索引自增可能越界的问题
     *
     * @param i        索引
     * @param capacity 数组的容量
     * @return 自增后的索引
     */
    static int inc(int i, int capacity) {
        return ++i >= capacity ? 0 : i;
    }

    /**
     * <h3>包级私有，当前包其他类可访问此方法，外部不可访问</h3>
     * <h3>而且此方法与当前类的实例无关，所以加static，而且可以与实例方法区分开来</h3>
     * <strong>不加private修饰以及增加一个capacity变量是为了破坏封装性，在同一个包内都能使用此方法进行已知容量的数组索引自增操作</strong><br><br>
     * 处理每次右端出队和左端入队时索引自减可能越界的问题
     *
     * @param i        索引
     * @param capacity 数组的容量
     * @return 自增后的索引
     */
    static int dec(int i, int capacity) {
        return --i < 0 ? capacity - 1 : i;
    }

    /**
     * 向双端队列左端加入元素
     * @param value 待入队的值
     * @return 入队成功返回true
     */
    @Override
    public boolean offerFirst(E value) {
        if (isFull()){
            return false;
        }
        head = dec(head, arr.length);
        arr[head] = value;
        return true;
    }

    /**
     * 向双端队列右端加入元素
     * @param value 待入队的值
     * @return 入队成功返回true
     */
    @Override
    public boolean offerLast(E value) {
        if (isFull()){
            return false;
        }
        arr[tail] = value;
        tail = inc(tail, arr.length);
        return true;
    }

    /**
     * 向双端队列左端获取元素并删除
     * @return 双端队列左端获取元素
     */
    @Override
    public E pollFirst() {
        if (isEmpty()){
            return null;
        }
        E value = arr[head];
        // 如果是基本类型，不用释放，例如int初始化为0还是四个字节，
        // 但是这里用了泛型，未来会被具体的对象替代，数组里面存的指针（对象的地址），
        // 指针指向这个对象，属于引用类型，该数组元素指向一个对象实例，
        // 当对象实例没有人指向它时才会被垃圾回收，所以这里要去掉指向该对象实例的指针
        arr[head] = null;
        head = inc(head,arr.length);
        return value;
    }

    /**
     * 向双端队列右端获取元素并且删除
     * @return 双端队列右端获取元素
     */
    @Override
    public E pollLast() {
        if (isEmpty()){
            return null;
        }
        tail = dec(tail,arr.length);
        E value = arr[tail];
        // 如果是基本类型，不用释放，例如int初始化为0还是四个字节，
        // 但是这里用了泛型，未来会被具体的对象替代，数组里面存的指针（对象的地址），
        // 指针指向这个对象，属于引用类型，该数组元素指向一个对象实例，
        // 当对象实例没有人指向它时才会被垃圾回收，所以这里要去掉指向该对象实例的指针
        arr[tail] = null;
        return value;
    }

    /**
     * 双端队列左端获取元素
     * @return 双端队列左端获取元素
     */
    @Override
    public E peekFirst() {
        if (isEmpty()){
            return null;
        }
        return arr[head];
    }

    /**
     * 双端队列右端获取元素
     * @return 双端队列右端获取元素
     */
    @Override
    public E peekLast() {
        if (isEmpty()){
            return null;
        }
        return arr[dec(tail, arr.length)];
    }

    /**
     * 判断双端队列是否为空
     *
     * @return 为空返回true
     */
    @Override
    public boolean isEmpty() {
        return tail == head;
    }

    /**
     * 判断双端队列是否为满
     *
     * @return 为满返回true
     */
    @Override
    public boolean isFull() {
        return inc(tail, arr.length) == head;
    }

    /**
     * 获取双端队列的大小
     * @return 双端队列的大小
     */
    @Override
    public int size() {
        return tail > head ? tail - head : tail + arr.length - head;
    }

    /**
     * 迭代器
     * @return 迭代器
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int index = head;
            @Override
            public boolean hasNext() {
                return index != tail;
            }

            @Override
            public E next() {
                E value = arr[index];
                index = inc(index,arr.length);
                return value;
            }
        };
    }

    /**
     * 扩容
     * @param capacity 容量
     * @throws IllegalArgumentException 传入的容量大小小于原始的容量大小
     */
    @SuppressWarnings("all")
    public void expansion(int capacity){
        int size = this.size();
        int index = 0;
        if (capacity < size){
            throw new IllegalArgumentException("参数"+capacity+"不能比"+ size +"小");
        }
        E[] array = (E[]) new Object[capacity + 1];
        for (E value : this) {
            array[index++] = value;
        }
        head = 0;
        tail = index;
        arr = array;
    }
}
